package com.gitee.alg.sort

/**
 * Project Name: alg
 * Des:希尔排序-- 直接插入排序的升级版
 * Package:com.gitee.alg.sort
 * @author Arlo Sun
 * @date 2021/4/26 - 21:56
 */
class ShellSort<T : Comparable<T>>(override val compare: (T, T) -> Boolean) : ArraySort<T> {

    override fun sort(array: Array<T>, ascend: Boolean): Array<T> {

        var step = gap(array.size)
        while (step >= 1) {

            for (i in step until array.size) {
                //待插入的数据
                val pivot = array[i]
                var j = i - step
                while (j >= 0 && compare(array[j], pivot)) {
                    array[j + step] = array[j]
                    //如果发生移动,则还需要继续往前找看是否还需要移动更前面的
                    j -= step
                }
                array[j + step] = pivot
            }

            step = (step + 1) / 2 - 1
        }

        return array
    }


    // 遵循 2^k -1  公式 ,中上效率，返回最大gap
    private fun gap(length: Int): Int {
        var gap = 1

        while (gap < length) {
            gap = gap * 2 + 1
        }

        return gap
    }
}


